#include <sstream>
#include <algorithm>
#include <stdexcept>
#include <fstream>
#include <limits>

#include "graph.hh"
#include "string.hh"
#include "debug.hh"

namespace icesp
{
    namespace graph
    {
        edge::weight_type constexpr edge::weight_max_value;
        int constexpr result_max{30000000};

        template <class T>
        void bin_read(std::istream& i, T* x)
        {
            i.read(reinterpret_cast<char*>(x), sizeof(*x));
            if (!i) throw std::runtime_error{"binary read failed"};
        }

        template <class T>
        void bin_read_n(std::istream& i, T* x, int size)
        {
            i.read(reinterpret_cast<char*>(x), sizeof(*x) * size);
            if (!i) throw std::runtime_error{"binary read failed"};
        }

        // TODO superfluous?
        template <class T>
        T bin_read(std::istream& i)
        {
            T x;
            bin_read(i, &x);
            return x;
        }

        template <class T>
        void bin_write(std::ostream& o, T* x)
        {
            o.write(reinterpret_cast<char*>(x), sizeof(*x));
            if (!o) throw std::runtime_error{"binary write failed"};
        }

        template <class T>
        void bin_write_n(std::ostream& o, T* x, int size)
        {
            o.write(reinterpret_cast<char*>(x), sizeof(*x) * size);
            if (!o) throw std::runtime_error{"binary write failed"};
        }

        adj_matrix::adj_matrix(std::string const& filepath)
            : tos(nullptr), ws(nullptr), pad_color(nullptr), pad_old(nullptr),
                new_node(nullptr), new_node_map(nullptr)
        {
            if (utils::ends_with(filepath, "obj.gr")) {
                PRINT3("read graph from object file: ", filepath, "\n");
                // read from obj file, dump from memory
                // TODO std::ios::binary, necessary?
                std::ifstream fin{filepath, std::ios::binary};
                if (!fin) throw std::runtime_error{"failed to open graph file"};
                bin_read(fin, &n);
                bin_read(fin, &m);

                // FIXME in case of n too large
                result.resize(std::min(result_max, n));

                edges.resize(m);
                bin_read_n(fin, edges.data(), edges.size());
                edge_index.resize(n + 1);
                bin_read_n(fin, edge_index.data(), edge_index.size());

                 index.resize(n);
                rindex.resize(n);
            } else {
                PRINT3("read graph from text file: ", filepath, "\n");
                // read from text file, parse it manually
                // format:
                // c comment
                // p sp n m
                // a from to cost
                // ...
                // TODO reconstruct
                std::ifstream fin{filepath};
                std::string line;
                do {
                    std::getline(fin, line);
                } while (!line.empty() && line[0] != 'p');
                if (line.empty())
                    throw std::runtime_error{"text input graph file: format error"};
                {
                    std::istringstream buf{line};
                    char ch;
                    buf >> ch >> ch >> ch >> n >> m;
                }

                // FIXME in case of n too large
                result.resize(std::min(result_max, n));

                 index.resize(n);
                rindex.resize(n);
                edge_index.resize(n + 1);
                edges.resize(m);

                PRINT("reading edges:");
                // DEBUG_PROC("reading edges: ");
                for (auto i = 0; i < m; i++) {
                    // DEBUG("reading " << i << "th edge.");
                    do {
                        std::getline(fin, line);
                    } while (!line.empty() && line[0] != 'a');
                    if (line.empty())
                        throw std::runtime_error{"text input graph file: format error"};
                    std::istringstream buf{line};
                    char ch;
                    buf >> ch >> edges[i].from >> edges[i].to >> edges[i].weight;
                    edges[i].from--;
                    edges[i].to--;
                }
                PRINT2(" ", "done\n");
                // DEBUG_PROC_DONE();

                PRINT("sorting edges:");
                // DEBUG_PROC("sorting edges: ");
                // TODO sort edges
                std::sort(edges.begin(), edges.end(),
                    [](edge const& lhs, edge const& rhs) {
                        return
                            std::tie(lhs.from, lhs.to, lhs.weight) <
                            std::tie(rhs.from, rhs.to, rhs.weight);
                    });
                PRINT2(" ", "done\n");
                // DEBUG_PROC_DONE();

                PRINT("building edge index:");
                // DEBUG_PROC("building edge index: ");
                build_index();
                PRINT2(" ", "done\n");
                // DEBUG_PROC_DONE();
            }
            PRINT2("number of nodes: ", n);
            PRINT2(",  number of edges: ", m << "\n");
        }

        void adj_matrix::dump_to_obj(std::string const& filepath)
        {
            std::ofstream fout{filepath, std::ios::binary};
            bin_write(fout, &n);
            bin_write(fout, &m);
            bin_write_n(fout, edges.data(), edges.size());
            bin_write_n(fout, edge_index.data(), edge_index.size());
        }

        void adj_matrix::reset_result()
        {
            std::fill(result.begin(), result.end(), edge::weight_max_value);
        }

        void adj_matrix::free_and_allocate_int_array(int* & p, int n)
        {
            if (p != nullptr) delete[] p;
            p = new int[n];
        }

        void adj_matrix::build_index()
        {
            std::fill(edge_index.begin(), edge_index.end(), -1);
            for (int i = 0; i < m; i++)
                if (edge_index[edges[i].from] == -1)
                    edge_index[edges[i].from] = i;
            edge_index[n] = m;
            for (int i = n - 1; i >= 0; i--)
                if (edge_index[i] == -1)
                    edge_index[i] = edge_index[i + 1];
        }

        void adj_matrix::realloc_result_pad()
        {
            result.clear();
            result.resize(std::min(result_max, n_after_pad));
        }

        void adj_matrix::pad(int npad, int* colors)
        {
            auto ncount = 0;
            free_and_allocate_int_array(new_node, n);
            free_and_allocate_int_array(new_node_map, n);

            for (auto i = 0; i < n; i++) {
                auto nedge = edge_index[i + 1] - edge_index[i];
                new_node_map[i] = ncount;
                if (nedge <= npad) new_node[i] = 1;
                else new_node[i] = (nedge - npad + npad - 3) / (npad - 2) + 1;
                ncount += new_node[i];
            }

            free_and_allocate_int_array(tos, ncount * npad);
            std::fill(tos, tos + ncount * npad, std::numeric_limits<int>::min());
            free_and_allocate_int_array(ws, ncount * npad);
            free_and_allocate_int_array(pad_color, ncount);
            free_and_allocate_int_array(pad_old, ncount);
            for (auto i = 0; i < n; i++) pad_old[i] = -1;
            for (auto i = 0; i < n; i++) {
                int cur = new_node_map[i];
                pad_color[cur] = colors[i];
                pad_old[cur] = i;
                int ne = 0;
                for (auto j = edge_index[i]; j < edge_index[i + 1]; ) {
                    auto to = new_node_map[edges[j].to];
                    auto  w = edges[j].weight;
                    if (ne != npad - 1) {
                        tos[cur * npad + ne] = to;
                        ws[cur * npad + ne] = w;
                        ne++; j++;
                    } else if (j == edge_index[i + 1] - 1) {
                        tos[cur * npad + ne] = to;
                        ws[cur * npad + ne] = w;
                        ne++;
                        break;
                    } else {
                        tos[cur * npad + ne] = cur + 1;
                        ws[cur * npad + ne] = 0;
                        ne = 0; cur++;
                        pad_color[cur] = colors[i];
                        tos[cur] = i;
                        tos[cur * npad + ne] = cur - 1;
                        ws[cur * npad + ne] = 0;
                        ne++;
                    }
                }
                while (ne != npad) {
                    tos[cur * npad + ne] = cur;
                    ws[cur * npad + ne] = 1;
                    ne++;
                }
            }
            n_after_pad = ncount;
        }

        void renumber(graph::adj_matrix& g, painter& p)
        {
            auto& n = g.n;
            auto& m = g.m;
            auto&  index = g. index;
            auto& rindex = g.rindex;
            auto& node_number_count = p.node_number_count;

            std::vector<int> tmp(p.nthread);

            tmp[0] = 0;
            for (int i = 1; i < p.nthread; i++)
                tmp[i] = tmp[i - 1] + node_number_count[i - 1];
            for (int i = 0; i < n; i++) {
                auto& co = p.colors[i];
                index[i] = tmp[co];
                rindex[tmp[co]] = i;
                tmp[co]++;
            }

            std::vector<graph::edge> edges(m);
            std::vector<int> edge_index(n + 1);

            for (auto i = 0, j = 0; i < n; i++) {
                auto& v = rindex[i];
                for (int k = g.edge_index[v]; k < g.edge_index[v + 1]; j++, k++) {
                    edges[j].from   = index[g.edges[k].from];
                    edges[j].to     = index[g.edges[k].to];
                    edges[j].weight = g.edges[k].weight;
                }
            }

            std::swap(edges, g.edges);
            std::swap(edge_index, g.edge_index);

            g.build_index();

            // TODO build color label
        }
    }
}

